package String.easy;

import java.util.HashMap;

/**
 * 1. 问题描述
 *      给你一个仅包含小写英文字母和 '?' 字符的字符串 s，请你将所有的 '?' 转换为若干小写字母，
 *      使最终的字符串不包含任何 连续重复 的字符。
 *      注意：你 不能 修改非 '?' 字符。
 *
 *      题目测试用例保证 除 '?' 字符 之外，不存在连续重复的字符。
 *      在完成所有转换（可能无需转换）后返回最终的字符串。如果有多个解决方案，请返回其中任何一个。
 *      可以证明，在给定的约束条件下，答案总是存在的。
 *
 * 2.算法思路
 *      如果单纯的只是替换字符串中的出现的?是一道非常简单的题，我们仅仅一次遍历即可实现。但是注意到题目中要求的替换
 *      之后的字符串不能出现连续的字符串形式。
 *
 *      还是通过一次遍历的方式，在遇到?的时候，获取?的前一个字符和后一个字符，如果没有用' '(代替，注意不能使用空字符'')
 *      设置一个临时temp = 'a'用于在26个字符中找到一个合适的字符赋予给当前chars[i]
 *
 *      时间复杂度：外层循环O(n),内层循环O(26),所以总的时间复杂度为O(26*n),实际上此算法的时间复杂度还是比较高的
 *
 *      另外一种解题思路：
 *          设置一个pre：记录当前字符的前一个字符，初始时定义pre = ' ',分两种情况：
 *          当前字符为?时，我们还是设置一个临时字符temp = 'a',用于找到一个合适的字符来替换当前的?,一旦找到了一个合适的字符
 *          我们将该字符赋给?,并且此时的pre修改为替换字符，如果当前的字符不是？，仅仅修改pre为当前字符即可
 *
 *
 * 3.具体的代码求解
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */



public class 替换字符串中出现的所有问号 {
    public static void main(String[] args) {
        String s1 = "?zs";
        String s2 = "ubv?w";
        String s3 = "j?qg??b";
        String s4 = "??yw?ipkj?";
        System.out.println(modifyString(s1));
    }

    // 算法1
    public static String modifyString(String s) {
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '?') {
                // 获取当前字符的前一位
                char ahead = i == 0 ? ' ' : chars[i-1];
                // 获取当前字符的后一位
                char behind = i == chars.length - 1 ? ' ' : chars[i+1];
                // 创建一个用于遍历比较的temp字符
                char temp = 'a';
                // 此时我们需要找到一个既不等于ahead并且又不等于behind的字符
                while (temp == ahead || temp == behind) {
                    temp++; // 此时会发生一个自动转型 char---int
                }
                chars[i] = (char) temp; // 在将int---char
            }
        }
        return new String(chars);
    }

    // 算法2
    public static String modifyString2 (String s) {
        char[] chars = s.toCharArray();
        char pre = ' ';
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '?') {
                char tmp = 'a';
                char behind = i == chars.length - 1 ? ' ' : chars[i+1];
                while (tmp == pre | tmp == behind) {
                    tmp++;
                }
                chars[i] = (char) tmp;
                pre = tmp;
            } else {
                pre = chars[i];
            }
        }
        return  new String(chars);
    }
}
